1. Field of the Invention
The present invention relates to a technology for calculating multicast paths in a multicast communication network. More particularly, the present invention relates to a technology for calculating efficient multicast paths from a source node to each destination node for transmitting multicast traffic.
2. Description of the Related Art
Attention is being given to multicast communication for delivering moving images and voices to a plurality of specific users on a computer network. In the multicast communication network, a source node is connected to destination nodes via a rendezvous point node at which a path is divided into a plurality of paths to the destination nodes. At the rendezvous point node, multicasted data are copied and transferred over the plurality of paths to the destination nodes.
As for unicast communication in which a source node is connected to each destination node in a one-to-one relationship, the source node needs to prepare copies of information the number of which is the same as that of the destination nodes. Thus, by using multicast communication, the amount of information transmitted over the network can be decreased.
In multicast communication, a set of destination nodes is called a multicast group, and a set of multicast paths are established from the source node to each node of the multicast group. The multicast paths are established such that the source node is connected to all of the destination nodes that belong to the multicast group. A user who wants to obtain information that is transferred to a multicast group joins the multicast group. Thus, the multicast paths change according to the joining state of users.
There are a plurality of applications that utilize multicast communication, such as videoconferences, on-line games, and applications for delivering moving images such as movies and television programs. As to the videoconferences and the on-line games, destination nodes correspond to a plurality of users, in addition, each of the plurality of users may become a source node when responding to received data. As for such applications, attention is being given to a technology for equalizing times at which each user responds to data transmitted via the multicast network so that occasion of response is equalized for each user. For equalizing the response times, there is a technology in which multicast paths from the source node to each destination node are designed such that similar delay arises in each multicast path.
Differences among delays along the paths between the source node and each destination node are called delay variation among users. However, currently, algorithms for calculating minimum delay paths are mainly used, and there is no communication method adopting an algorithm for calculating paths in consideration of the delay variation among users. There are following conventional examples of algorithms for decreasing delay variation among users:
Document 1: G, Rouskas, et. al., “Multicast Routing With End-to-End Delay and Delay Variation Constraints”, IEEE Journal on Selected Areas in Communication, Vol 15, NO. 3, April 1997.
Document 2: Pi-Rong Sheu, et.al., “A Fast and Efficient Heuristic Algorithm for the Delay and Delay Variation Bound Multicast Tree Problem”, IEEEICC, 2001.
The document 1 is the first document that try to solve the above-mentioned problem. Following is the method for calculating paths according to the document 1.
First, each minimum delay path between a source node and each destination node is calculated, and a delay w of a path that has maximum delay among the minimum delay paths is checked. Assuming that is delay variation acceptable by an application (this parameter means that the difference of the maximum end-to-end delay and the minimum end-to-end delay among the paths from the source node to all the destination nodes has to be kept within ), paths which satisfy di≦w− are adopted in which di indicates a delay between the source node and the destination node i. As for a path that is not adopted, a path that satisfies the condition is searched for by using an algorithm for searching for a k-th shortest path. Then, the searched path is adopted. Assuming that the number of the destination nodes is m and the number of nodes in the network is n, then the computation time complexity of this method is O(kmn3).
In the document 2, a method is proposed in which the time complexity is smaller than that of the document 1, so that calculation time for obtaining paths is shortened. The method of calculation is as follows.
The multicast paths include an one-to-one unicast path between the source node and a rendezvous point node (that can be also called as a central node) and one-to-many paths between the rendezvous point node and each destination node. In the method of document 2, the minimum delay between each destination node and each other node in the network is calculated first. Next, for each node in the network, associated multicast delay variation between the node and each destination node is calculated. Then, a node with the minimum multicast delay variation is selected as the rendezvous point node. Finally, each destination node is connected to this rendezvous point node through the minimum delay path, the source node is also connected to the rendezvous point node through the minimum delay path. The time complexity of this method is O(n3), and calculation faster than document 1 can be realized.
There are following problems in the above-mentioned conventional technologies.
According to the above-mentioned two calculation methods, the time complexity becomes large. Since applications that require decrease of the delay variation generally need real-time processing, it is desirable to decrease time complexity. In addition, it is requested to decrease transmission delay for the real-time applications. As for the method of the document 2 in which rendezvous point is provided, it is pointed out that realizing minimum delay path is generally difficult. Therefore, there is a problem in that the transmission delay to each destination node becomes generally large according to the method of the document 2.
When establishing the multicast communication network, from the viewpoint of establishing multicast paths efficiently between a source node and each destination node, a minimal tree problem is known in which total cost of the multicast paths is minimized. This problem is called a Steiner tree problem. The Steiner tree problem is known as NP problem in which it is impossible to calculate paths that form an optimal minimal tree from the source node to each destination node in a finite calculation time if the size of the network is large.
Although to obtain the ideal solution of the Steiner problem is NP hard, a calculation method for heuristically deriving an approximated solution is proposed as KMB communication method (refer to document 3: L. Kou, G. Markowsky, and L. Berman, “A Fast Algorithm for Steiner Tree,” Acta Informatica 15, 1981, pp. 141-145.).
In this method, the source node and the destination node group are extracted, and a graph formed by edges each corresponding to a shortest path between extracted nodes is constructed first. From the constructed graph, a minimal spanning tree is constructed. Then, each edge of the spanning tree is replaced by shortest path of the input graph to construct a subgraph. Then, a minimal spanning tree is found from the subgraph. Finally, multicast paths (Steiner tree) are constructed by deleting unnecessary edges from the spanning tree.
However, according to the multicast path calculation method of the document 3, although the transfer cost of the whole multicast paths can be minimized, the method does not consider the cost (delay) variation from the source node to each destination node. Thus, the cost variation becomes very large. Therefore, when applying this calculation method to the real-time application that does not permit large delay variation, there is a large problem in that large delay variation occurs among multicast receivers.